/**
 *    FreeRaven   is an high-power, tiny-footprint, open source  
 *                javascript CSS  selector engine.
 * It supports most CSS3 selectors with more to come. It is realeased
 * under the MIT license and may be used by anyone for opensource or 
 * commercial development.  The only request I have, however, is that
 * when asked, I receive credit for the work done here.  Other than that
 * enjoy! :)
 *
 * @author Rick Allen <stoodder@gmail.com>
 *
 * TODO: 
 * - finish pseudo selectors
 *   - not()
 *   - contains()
 *   - nth-last-child()
 * - allow for * when doing descendants/child sectors (<, +, ~)
 * - Allow for multiple selections, things separated by ,
 */
 (function() 
 {
	 //variable that represents the internal cache table, generated during execution
	 //This works by building a 'tree' of css selectors for a given root element. This
	 //allows us to decend down the tree skipping calculations for each sub css part
	 //found from the overall css string. Basically, we cache the results at each 
	 //intermediate subcss step.
	 var _cache = {}, 
	 
	 //the current cache id, used to add elements on to the cache table
	 cid = 0,
	 
	 //they key in the cache to look at (usually this will just be the subcss but 
	// changes when we're using an attribute slector or pseudo selctor. 
	 cacheKey,
	 
	 //flag to determine if we should use cache or not, true by default, determined later
	 useCache = true,
	 
	 //variable used to store a reference to the root element that was called
	 root,
	
	//the current partial select based on values found with the 'subcss' string
	_select, 
	
	//internal iterator used to push _select with new elements
	_i, 
	
	//internal iterator used to look at elements returned from offspring or descendant
	//lookups
	_j, 
	
	//the state of the selector, used to determine if at a current subcss lookup an element
	//has already been analyzed, necessary for keeping each element in _select unique
	state = 0,  
	
	//variable used to store the 'parts' of the total css string, separated by a space	
	parts, 
	
	//the iterator tracking the spot in parts (may be used to help 'jump ahead' in the 
	//parts array, if we ever use an optimization like this
	i, 
	
	//an array containing all strings found in the css string (anything with '' or "" 
	//around it)
	strings, 
	
	//another array like strings that captures all equations (such as 2n or 2n-1) between ( )
	equations,
	
	//the subcss we are currently look at (for now this is a reference to the current 
	//index in parts
	subcss, 
	
	//variable used in selector that represents the tagName to look for (based on what 
	//is in the subcss variable
	tagName, 
	
	//variable used to determine the class name to look for in the current element
	className, 
	
	//variable used to determein and store the id of an element based on the css
	id,
	
	//variable used for storing the name of the attribute to look at in the current element
	attr, 
	
	//varibale used to store the attribute value to look at in the current element
	value, 
	
	//a variable used to store the descendants returned from an element
	descendants, 
	
	//variable used to store the offspring returned from an element
	offspring,
	
	//variable used to store a parent element
	parent,
	
	//variable used to store the length that a loop
	length; 
	
	//internal method used to get an element's next sibling element
	_next = function(element)
	{
		//get the initial next element
		var next = element.nextSibling; 
		
		//keep looping until we find an HTML element
		while( next )
		{
			//return the element
			if( next.tagName )
				return next;
			
			//keep goind
			next = next.nextSibling;
		}
		
		//nothing found here.
		return null;
	};
	
	//internal method used to get an element's previous sibling element
	_prev = function(element)
	{
		//do we have the first element chached?	
		var prev = element.previousSibling; 
		
		//keep looping until we find an HTML element
		while( prev )
		{
			if( prev.tagName )
				return prev;
			
			prev = prev.previousSibling;
		}
		
		return null;
	};
	
	//internal method used to get the first child element in the given element
	_first = function(element)
	{
		//do we have the first element chached?
		child = element.firstChild;
			
		while( child )
		{
			if( child.tagName )
				return child;
			
			child = child.nextSibling;
		}
		
		return null;
	};
	
	//internal method used to get the first child element in the given element
	_last = function(element)
	{
		//do we have the first element chached?
		child = element.lastChild;
			
		while( child )
		{
			if( child.tagName )
				return child;
			
			child = child.previousSibling;
		}
		
		return null;
	};
	
	//method used to get the index of an element within it's parent
	_index = function(element)
	{
		//have we already looked at this element?
		if( element._fr_state == state )
			return element.index; //simply pass back the index
		
		var child = _first(element.parentNode),
		index = -1;
		
		while( !!child )
		{
			child.index = ++index;
			child._fr_state = state;
			child = _next(child);
		}
		
		return element.index;
	};
	
	//internal method used to get the parent node of the current element
	_parent = function(element)
	{
		return element.parentNode;
	};
	
	//method used to mimic the break; operator
	_break = function()
	{
		throw _break;
	};
	
	// Object used to get a method that will filter and format the current subcss part
	_filter = {
		/*----------------------------------------------------------------*/
		//match all descendant elements
		/*----------------------------------------------------------------*/
		"*" : function() 
		{
			return ( i > 0 ?
				function (element) 
				{
					//have we already looked at this element?
					if(element._fr_state == state)
						return;
						
					descendants = element.getElementsByTagName("*"),
					length = descendants.length;
					
					for(_j = 0; _j < length; ++_j)
						( _select[++_i] = descendants[_j] )._fr_state = state;
				}
				: function (element)
				{
					_select = element.getElementsByTagName("*");
				}
			);
		},

		/*----------------------------------------------------------------*/
		//match IDs
		/*----------------------------------------------------------------*/
		"#" : function()
		{
			//get the id off the subcss string
			id = subcss.slice(1);
			
			//pass back the iteration method
			return function (element) 
			{
				//does the element's id match the reuqested id?
				if ( element.id == id )
				{
					_break( _select = [element] ); //set the select as this element and 
												   //break out, there really should only 
												   //be one with this ID
				}
			};
		},

		/*----------------------------------------------------------------*/
		//match classes
		/*----------------------------------------------------------------*/
		"#" : function()
		{
			//make it into a regular expression to check
			id = subcss.slice(1);
			
			//method used to determine if this element has the requested id
			return function(element)
			{
				if( element.id == id )
					_break( _select = [element] );
			};
		},

		/*----------------------------------------------------------------*/
		//match classes
		/*----------------------------------------------------------------*/
		"." : function()
		{	
			//make it into a regular expression to check
			className = " " + subcss.slice(1)+  " ";
			
			return function(element)
			{
				if ( (" " + element.className + " ").indexOf(className) > -1 )
					_select[++_i] = element;
					
				descendants = element.getElementsByTagName("*"),
				length = descendants.length;
				
				for( _j = 0; _j < length; ++_j )
					if ( (" " + descendants[_j].className + " ").indexOf(className) > -1 )
						_select[++_i] = descendants[_j];
			};
		},

		/*----------------------------------------------------------------*/
		//match children
		/*----------------------------------------------------------------*/
		">" : function(){
			//get the tag name (if there is a >, +, or ~ in front)
			tagName =  subcss.slice(1).toUpperCase();

			return function (element)
			{
				offspring = _first(element);
				while( !!offspring )
				{
					if(offspring.tagName == tagName)
						_select[++_i] = offspring;
					offspring = _next(offspring);
				}
			};
		},

		/*----------------------------------------------------------------*/
		//match next adjacent element
		/*----------------------------------------------------------------*/
		"+" : function()
		{
			//get the tag name (if there is a >, +, or ~ in front)
			tagName =  subcss.slice(1).toUpperCase();

			return function(element)
			{
				//get the next sibline
				var next = _next(element);

				//if somehting was found and matches the tag, return it
				if ( !!next && next.tagName == tagName)
					_select[++_i] = next;
			};
		},

		/*----------------------------------------------------------------*/
		//match all next siblings
		/*----------------------------------------------------------------*/
		"~" : function()
		{
			//get the tag name (if there is a >, +, or ~ in front)
			tagName =  subcss.slice(1).toUpperCase();

			return function(element) 
			{
				if(element._fr_state == state)
					return;

				//get the next sibling
				var next = _next(element);

				//look at all next siblings as long as they are valid
				while ( !!next )
				{
					//notify that we've already looked at this element, 
					//and therefor also every element afterwards
					next._fr_state = state;
					
					//does _select tag name match the one we're looing for?
					if (next.tagName == tagName)
						_select[++_i] = next;

					//venture on to the next sibling
					next = _next(next);
				}
			}
		},

		/*----------------------------------------------------------------*/
		//match psuedo selctors
		/*----------------------------------------------------------------*/
		":" : function(){
			psuedo = subcss.toLowerCase();
			//return the specified method based on the psuedo selector
			return ({
				//defines the method used to find if _select element if the first element of it's parent
				':first-child': function (element) 
				{
					//if there is no more previous elements, _select is the first one
					if ( !_prev(element) ) 
						_select[++_i] = element; //append the matched element
				},
				
				//defined if this element is the last element of it's parent
				':last-child': function (element) 
				{
					//if there is no more elements left, _select is the last one
					if ( !_next(element) ) 
						_select[++_i] = element; //append the matched elemenr
				},
				
				//defines if this element is the only element in its parent
				':only-child': function (element) {
					//if _select has no siblings, it is the only child
					if ( !_next(element) && !_prev(element) ) 
						_select[++_i] = element; //append the matched element
				},
				
				//defines if the given element has no offspring
				':empty' : function(element)
				{
					//this is only empty if no children are found
					if( !_first(element) ) 
						_select[++_i] = element; //append the matched element
				},
				
				//selects an element if it is an even element of its parent ( 0 indexed )
				':even' : function(element)
				{
					if( _index(element) % 2 == 0 )
						_select[++_i] = element;
				},
				
				//selects an element if it is an even element of its parent ( 0 indexed )
				':odd' : function(element)
				{
					if( _index(element) % 2 == 1 )
						_select[++_i] = element;
				},
				//gets all input type elements
				':input' : function(element)
				{
					if( element.tagName.match(/input|textarea|button/i) )
						_select[++_i] = element;
				},
				//is this element enabled?
				':enabled' : function(element)
				{
					if( element.tagName.match(/input|textarea|button/i) && !element.disabled )
						_select[++_i] = element;
				},
				//is this element disabled?
				':disabled' : function(element)
				{
					if( element.tagName.match(/input|textarea|button/i) && !!element.disabled ) //Do we really need this regular expression?
						_select[++_i] = element;				
				},
				//is this element checked?
				':checked' : function(element)
				{
					if( !!element.checked )
						_select[++_i] = element;
				},
				//is this element not checked?
				':unchecked' : function(element)
				{
					if( ( element.type || "" ).match(/checkbox|radio/i) && !element.checked )
						_select[++_i] = element;
				},
				':password' : function(element)
				{
					//used to grab all of the password fields
					if( ( element.type || "" ).match(/password/i) )
						_select[++_i] = element;
				}
				//get the specified method in the hash map, 
			}[psuedo]
			//was this a special selctor such as nth-child()?
			|| (function()
				{
					//get the selctor's equation (might be an equation or simple selector for operations like not and has
					var equation = equations.shift(),
						a = 0,
						b = 0;
						function match_single() { 
							a = parseInt( equation.replace(/ /g, "").match(/\(([0-9]+)\)/)[1] || -1 ); 
						}
						function match_multi() { 
							var matches = equation.replace(/ /g, "").match(/\((([0-9]+)n[+]?)?([0-9]+)?\)/);
							a = parseInt( matches[2] || 0 ); //get a
							b = parseInt( matches[3] || 0 ); 
						}
					return ({
						':nth-child()' : function()
						{
							match_multi();
							var c = a-b; //this is used for the case where we have an+b, it reduces the number of calculations needed
							//return the matching eqaution
							return ( a > 0 && b > 0 ?
								//did we match something like #n+# (3n+1)
								function(element) //append the element id it did
								{
									var i = _index(element);
									if( i >= b && ( i + c ) % a < 1 ) _select[++_i] = element;
								}
							//otherwise did we match something like #n (3n)
							: ( a > 0 ?
								function(element) { if( _index(element) % a == 0 ) _select[++_i] = element; }
							//lastly just get by index # (3)
							: 	function(element) { if( _index(element) == b ) _select[++_i] = element; }
							));
						},
						':nth-last-child()' : function()
						{
							match_multi();
						},
						':gt()': function()
						{
							match_single();
							return function(element) { if( _index(element) > a ) _select[++_i] = element; }
						},
						':lt()': function()
						{
							match_single();
							return function(element) { if( _index(element) < a ) _select[++_i] = element; }
						},
						//TODO: consider getting rid of these, the same effect can come with a :gt():lt() combo move
						':eq()': function()
						{
							match_single();
							return function(element) { if( _index(element) == a ) _select[++_i] = element;}
						},
						':neq()': function()
						{
							match_single();
							return function(element) { if( _index(element) != a ) _select[++_i] = element; }
						}
						/**
						* TODO:
						* not
						* has
						* nth-last-child
						*/
					}[psuedo]
						|| function() { _select = []; _break() }
					)()
				})()
			)
		},

		/*----------------------------------------------------------------*/
		//match attribute selctor
		/*----------------------------------------------------------------*/
		"[" : function()
		{
			//get the index in the subcss of the '=' (if one exists)
			var index = subcss.indexOf("=");
			
			//if we didn't find one, simply look to see if we have the attrbute
			if(index == -1) 
			{
				//remove the [ and ] on either side of the subcss
				attr = subcss.slice(1, subcss.length-1);
				
				//pass back the iteration method to use
				return function (element) 
				{
					//does _select attribute exist?
					if ( !!element.getAttribute(attr) )
						_select[++_i] = element; //append the matched element
				};
			}

			value = strings.shift(); //get the next string off the strings list
		
			var func = {
				//return method, does the attribute start with the given cach value?
				"^": function (check) 
				{ 
					return ( check.substring(0, value.length) == value ); 
				},
				//return method, is the value found in a space separated list?
				"~": function (check) 
				{ 
					return ( (" " + check + " ").indexOf(" " + value + " ") > -1 ); 
				},
				//return method, is the check value found at the end of the attribute
				"$": function (check) 
				{ 
					return ( check.substring(check.length-value.length, check.length) == value ); 
				},
				//return method, is the check vaule found anywhere in the attribute?
				"*": function (check) 
				{ 
					return ( check.indexOf(value) > -1 ); 
				},
				//return method, is the check value found anywhere in he dash separated attribute
				"|": function (check) 
				{ 
					return ( ("-" + check + "-").indexOf("-" + value + "-") > -1 ); 
				},
				//return method, does the check value NOT exist in the aattribute
				"!": function (check) 
				{ 
					return ( (check).indexOf(value) == -1 ); 
				}
			}[subcss.charAt(index-1)]; //try to get the correct method
			
			//if no method found, resort to the default method and get the correct attribute string
			if( !func )
			{
				//set the checking function to default which is to simply compare the element's attribute 
				//against the requested value
				func = function(check) { return (value == check) };
				attr = subcss.slice(1);
			}
			//otherwise get the attribute and string off the special selector character
			else
			{
				attr = subcss.slice(1);
			}
			
			value = value.substring(1, value.length-1); //remove "" or ''
			
			//pass back he method to match the attribute based on the given selector
			return function (element) 
			{
				//get the attribute of the element
				if ( func( attr == 'class' ? element.className : element.getAttribute(attr) || "" ) )
					_select[++_i] = element; //append the matched element
			};
		}
	};

	/*----------------------------------------------------------------*/
	// Default filtering method to use, the subcss, if valid, will match a tag name
	/*----------------------------------------------------------------*/
	_defaultFilter = function()
	{
		//get and format the tag name
		tagName = subcss.toUpperCase();
		
		return ( i == 0 ?
			//if we are just grab all elements underneath this one with the given tag name
			function(element)
			{
				_select = element.getElementsByTagName(tagName); //cache key holds the Tag Name in this case
			}
			//otherwise append these elemts to the sub select for this css part
			: function(element) 
			{							
				//have we already looked at this element?
				if(element._fr_state == state) return;
				
				descendants = element.getElementsByTagName(tagName), //cache key holds the Tag Name in this case
				length = descendants.length;
				
				//look over the results and only add those who haven't already been added
				for(_j = 0; _j < length; ++_j)
					if( descendants[_j]._fr_state != state ) //is this already in the _select array?
						( _select[++_i] = descendants[_j] )._fr_state = state;
			}
		);

	};
	
	//define the default selector methodology
	function FreeRaven(css, element) 
	{
		//make sure the css is a string
		if (typeof css != 'string') return [];

		//get the root 'context' element
		root = ( !element ? document : ( typeof element == 'object' ? element : document.getElementById(element) ) );
		
		//if the element was invalid, pass back a blank array
		if( !root ) return [];
		
		//do we have access to faster internal methods?
		if( root.querySelectorAll )
			try { return root.querySelectorAll(css) } catch(e) {}
		
		//get all of the strings within the css
		strings = css.match(/("[^"]*")|('[^']*')/g); // get all strings in the css
		css = css.replace(/("[^"]*")|('[^']*')/g, "") //now remove all strings
		equations = css.match(/\([^)]+\)/g); // get all equations ( anything between ( and )
		css = css.replace(/\([^)]+\)/g, "()"); // now remove all of these equations
		//start "normalizing" the css string
		css = css	.replace(/([:#.+>[~])\s*/g, " $1") //put spaces between the necessary characters
					.replace(/\s+/g, " ") //remove all multiple white space
					.replace(/ ?([|^~$*]?=) ?/g, "$1") //if this is an attribtue selector, remove any white space between it.
					.replace(/\[ /, "[") //remove white space between []
					.replace(/ ?(.+) ?/, "$1"); //trim out any leading or trailing space
		
		//initialize our caching tree
		if( useCache )
		{
			root._fr_cid = ( root._fr_cid || ++cid );
			if( !_cache[root._fr_cid] )
				_cache[root._fr_cid] = {};
			var cache = _cache[root._fr_cid];
		
			//has this css be cached? return it if it has
			if( cache[css] )
				return cache[css]["@@cache"];
		}
		
		//if the css is empty, return nothing
		if( css.length == 0 ) return [];
		
		//get each of the parts
		var parts = css.split(" "),
		
		//reset the subcss parts select iterator
		i = -1;
		
		//TODO: consider caching this result
		//if we're starting with a class or ID just get the descendants, otherwise we must start with the root element
		/*var select = 
		({
			"." : function()
			{
				return ( root.getElementsByClassName ?
					root.getElementsByClassName( parts[0].slice(++i+1) )
					: [root]
				)
			},
			//if we're starting by looknig for an ID see if there are any browser specific methods to get an element by id
			"#" : function()
			{
				return ( root.getElementById ?
					//can the root grab by id? if so do it!
					[ root.getElementById( parts[0].slice(++i+1)) ]
					//otherwise grab everything
					: root.getElementsByTagName("*")
				)
			}
		}[ css.charAt(0) ]
			//otherwise just pass back the root element, no intial selections are needed
			|| function()
			{
				return [root];
			}
		)();*/
		
		//if we incremented then mak sure we consider this step with the cache
		if( useCache && i > -1) cache = cache[parts[0]] = {};
		
		//incremenet through the parts and set the subcss while we can
		while( subcss = parts[++i] )
		{
			if( useCache )
			{
				//set the intial cache key
				cacheKey = subcss;
				
				//if this a tag? make sure the cache key is upper case to avoid duplicate caching (table, TABLE)
				if( subcss.charAt(0).match(/[A-Za-z0-9-_>+~]/) )
					cacheKey = cacheKey.toUpperCase();
				//is this an attribute selctor with a comparison? extend the key to reflect this
				else if( subcss.indexOf("=") > -1 )
					cacheKey += strings[0];
				//is this a psuedo selector with an equations? extend the key to reflect this
				else if( subcss.indexOf(")") > -1 )
					cacheKey += equations[0];
			}
			
				
			//do we already have this step cached?
			if( useCache && cache[cacheKey] )
			{
				//simply retrieve from the cache
				select = cache[cacheKey]["@@cache"];
			}
			else
			{		
				_select = [], //reset the subselect
				_i = -1; //reset the sub select iterator
				
				try {
					var filter = ( _filter[ subcss.charAt(0) ] || _defaultFilter )(), //execute operations on the current subcss part and return the filter method
						size = select.length; //store the length of the currently selected elements for faster loops
					
					//iterate through each selected element and apply the current subcss part
					for( var j = 0; j < size; ++j) filter( select[j] ); //apply the filtering
				//were we intentionally trying to break out? if not propogate the error
				} catch (e) { if( e != _break ) throw e; }
				
				//since we didn't have the cache, create it
				if(useCache) cache[cacheKey] = { "@@cache" : _select };
				
				//store the newly selected nodes as the current selected value
				select = _select;
				
				//increment the state (needed for uniqueness of results)
				++state;
			}
			
			//go to the next level in the cache tree based on this subcss selector
			if( useCache )
				cache = cache[cacheKey];
			
			//if nothing is left in the selcect then there is no use in contirnuing
			if (select.length == 0) break;
		};
		
		if(useCache) _cache[root._fr_cid][css] = { "@@cache" : select };
		
		//return our results
		return select;
	}
	
	/**
	* Simple method to always get an array back from a FreeRaven execution.
	*
	* @param {String} css A String css selctor
	* @param {String} root The id of the element to be considered the root elemenet
	*/
	FreeRaven.array = function( css, root )
	{
		var array = [], //the array we will be pasing back
			raven = FreeRaven(css, root), //find the results
			length = raven.length; //store the length for quicker loops
		
		//if this is already an array don't even bother generating one
		if( Object.prototype.toString.call(raven) == '[object Array]' )
			return raven;
		
		//generate the array
		for( var i = 0; i < length; ++i )
			array[i] = raven[i];
		
		//return the result
		return array;
	};
	
	/**
	* Method used to remove the cache within FreeRaven
	*/
	FreeRaven.clearCache = function()
	{
		//delete _cache;
		_cache = [];
	}
	
	//apply some event listeners
	if( window.addEventListener )
	{
		//when the window loads, add DOM element listeners
		window.addEventListener('load', function()
		{
			//consider trying to add these to individual root elements instead of the whole document
			document.addEventListener('DOMNodeInserted', FreeRaven.clearCache, false);
			document.addEventListener('DOMNodeRemoved', FreeRaven.clearCache, false);
			document.addEventListener('DOMAttrModified', FreeRaven.clearCache, false);
		}, false);
	}
	//otherwise see if the attachEvent method is valid... IE...
	else if( window.attachEvent )
	{
		window.attachEvent('onload', function()
		{
			//create a "watching" method.  this will get applied to allelements current found in the DOM
			//this method gets triggered when something happens to one of the elements.  the cache will
			//then be cleared and we will re-assign the watch to elements below.
			var clearing = false, watch = function(){};
			watch = function(event) 
			{ 
				//don't execute this if we're in the process of clearing the cache already.
				//now if only there were a way to check if an attribute was actually an HTML attribute or not...
				if( clearing || event.propertyName.match(/_fr_(cid|state)/) && !( event.propertyName == "innerHTML" || event.propertyName in event.srcElement.attributes ) )
					return;
				clearing = true;
				//wait till the rest of the script execution is done to look at other elements
				setTimeout( function() {
					clearing = false;
					var element = event.srcElement;
					//now watch all elements below this
					var descendants = element.getElementsByTagName("*"),
						length = descendants.length;
					//atach the listener to all descendants	
					for( var i = 0; i < length; ++i)
						descendants[i].attachEvent("onpropertychange", watch);
				}, 0);
					
				//clear the cache
				FreeRaven.clearCache();
			};
			
			//watch everything
			var descendants = document.getElementsByTagName("*"),
				length = descendants.length;
			for( var i = 0; i < length; ++i)
				descendants[i].attachEvent("onpropertychange", watch);
			
		});		
	}
	else
	{
		//sorry everyone else, you aren't allowed to use caching
		useCache = false;
	}
	
	//show the rest of the internets
	window.FreeRaven = FreeRaven;
 })();